﻿using IceCS.DataStructure.Core.LinearList.Exceptions;
using System;

namespace IceCS.DataStructure.Core.LinearList
{

    /// <summary>
    /// 循环双向链表
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class CircularDoublyLinkedList<T> : ILinarList<T>
    {
        /// <summary>
        /// 
        /// </summary>
        public CircularDoublyLinkedList()
        {
            Head = null;
            Count = 0;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="item"></param>
        public void Add(T item)
        {
            if (IsEmpty)
            {
                Head = new ListNode<T>(item);
                Head.Next = Head;
                Head.Previous = Head;
                Count++;
                return;
            }
            else if (Count == 1)
            {
                var newNode = new ListNode<T>(item, Head, Head);
                Head.Next = newNode;
                Head.Previous = newNode;

            }
            else
            {
                ListNode<T> current = Head;
                while (current.Next != Head)
                {
                    current = current.Next;
                }

                var newNode = new ListNode<T>(item, Head, current);
                current.Next = newNode;
            }
            Count++;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="index"></param>
        /// <param name="item"></param>
        public void Insert(int index, T item)
        {
            if (!IsInRightIndexRange(index))
            {
                throw new IndexOutOfRangeException("指定索引超出范围");
            }

            if (index == 0) //插在第一个
            {
                Add(item);
                return;
            }
            var newNode = new ListNode<T>(item);
            ListNode<T> previous = GetPreviousNodeByIndex(index);
            ListNode<T> current = previous.Next;
            previous.Next = newNode;
            newNode.Previous = previous;
            newNode.Next = current;
            current.Previous = newNode;
            Count++;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="item"></param>
        public void Remove(T item)
        {
            if (IsEmpty)
            {
                throw new DSEmptyException();
            }
            if (Count == 1)
            {
                Head = null;
                return;
            }
            ListNode<T> previous = null;
            ListNode<T> current = Head;
            while (Count > 1)
            {
                if ((object)current.Data == (object)item)
                {
                    break;
                }
                else
                {
                    previous = current;
                    current = current.Next;
                }
            }
            //移除项是 head 节点
            if (previous == null)
            {
                var newHead = Head.Next;
                Head.Previous.Next = newHead;
                newHead.Previous = Head.Previous.Next;
                Head = newHead;
            }
            else
            {
                previous.Next = current.Next;
                current.Next.Previous = previous;
            }
            Count--;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="index"></param>
        public void RemoveAt(int index)
        {
            if (IsEmpty)
            {
                throw new DSEmptyException();
            }
            if (Count == 1)
            {
                Head = null;
                return;
            }

            if (!IsInRightIndexRange(index))
            {
                throw new IndexOutOfRangeException("指定索引超出范围");
            }

            if (index == 0)
            {
                var newHead = Head.Next;
                Head.Previous.Next = newHead;
                newHead.Previous = Head.Previous.Next;
                Head = newHead;
            }
            else
            {
                ListNode<T> previous = GetPreviousNodeByIndex(index);
                ListNode<T> current = previous.Next;
                previous.Next = current.Next;
                current.Next.Previous = previous;
            }
            Count--;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public T FindIndex(int index)
        {
            if (IsEmpty || !IsInRightIndexRange(index))
            {
                throw new IndexOutOfRangeException("指定索引超出范围");
            }
            if (index == 0)
            {
                return Head.Data;
            }
            ListNode<T> previous = GetPreviousNodeByIndex(index);
            ListNode<T> current = previous.Next;
            return current.Data;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="match"></param>
        /// <returns></returns>
        public T Find(Func<T, bool> match)
        {
            if (IsEmpty)
            {
                throw new DSEmptyException();
            }
            ListNode<T> current = Head;
            ListNode<T> foundItem = null;
            while (current != null)
            {
                if (match(current.Data))
                {
                    foundItem = current;
                    break;
                }
                else
                {
                    current = current.Next;
                }
            }
            if (foundItem == null)
            {
                return default;
            }
            else
            {
                return foundItem.Data;
            }
        }

        /// <summary>
        /// 
        /// </summary>
        public void Clear()
        {
            Head = null;
            Count = 0;
        }

        /// <summary>
        /// 单链表的头引用
        /// </summary>
        public ListNode<T> Head { get; private set; }

        /// <summary>
        /// 
        /// </summary>
        public bool IsEmpty => Head == null;

        /// <summary>
        /// 
        /// </summary>
        public bool IsFull => false;

        /// <summary>
        /// 
        /// </summary>
        public int Count { get; private set; }

        /// <summary>
        /// 是否在正确的索引范围内
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        private bool IsInRightIndexRange(int index) => index >= 0 && index < Count;

        /// <summary>
        /// 找到索引节点的上一个节点
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        private ListNode<T> GetPreviousNodeByIndex(int index)
        {
            //第一个节点无上一个节点
            if (index == 0)
            {
                return null;
            }

            ListNode<T> previous = Head;
            //控制循环
            int i = 1;
            //从开始的节点通过遍历找到插入位置的前一个节点
            //只有index 大于等于2才走循环查找下一个
            while (i < index)
            {
                previous = previous.Next;
                i++;
            }
            return previous;
        }
    }
}
